class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [1] * (n+1)
        if n == 2:
            return 1
        if n == 3:
            return 2
        for i in range(2,n+1):
            for j in range(0,i):
                dp[i] = max(dp[i], dp[j]*(i-j))
        return dp[-1]

if __name__ == '__main__':
    so = Solution()
    nums1 = 10
    r = so.integerBreak(nums1)
    print(r)
